/////////////////////////////////////////////////////////////////////////
//
// Amuse Engine SDK - core/containers
// Copyright( c) 2014.  All Rights Reserved
//
// File:		AECachedHashMap.cpp
// Author:		Gianluca Belardelli
// Date:		20/10/2014
//
/////////////////////////////////////////////////////////////////////////
#include <AECore.h>

#define HASH_EMPTY AEUINT32(-1)

// Quick description:
// The uiHash table is stored as a linear list. Initially all keys
// are 0xff (empty). When we Insert an element, we jump to the items
// uiHash and scan forwards until we find the uiKey or we come to an empty entry.
// If the uiHash function is good and the table is not too crowded, we're
// likely to have good performance and be cache friendly.
// The first third of m_lpElem are the hashes, the second third the string pointers
// and the final third, the uiValue pointers.

#define ELEM_HASH(i) (m_lpElem[i].uiHash)
#define ELEM_KEY(i)  (m_lpElem[i].uiKey)
#define ELEM_VAL(i)  (m_lpElem[i].uiValue)

#define NOT_EQUAL(i,uiHash,uiKey,ops) ((ELEM_HASH(i) != uiHash) || (ops.Equal( uiKey, ELEM_KEY(i) ) == 0))
#define Equal(i,uiHash,uiKey,ops) ((ELEM_HASH(i) == uiHash) && (ops.Equal( uiKey, ELEM_KEY(i) ) ))

template<typename Operations, typename AEAllocator>
AECachedHashMap<Operations, AEAllocator>::AECachedHashMap( Operations ops ) : m_objOps(ops)
{
	const int nInitialCapacity = 16;
	AEMemoryAllocator &memAlloc = AEAllocator().Get( this );
	m_lpElem = memAlloc._blockAlloc<Elem>( nInitialCapacity );
	hkString::memSet( m_lpElem, 0xff, sizeof(Elem) * nInitialCapacity );
	m_uiNumElems = 0;
	m_uiHashMod = nInitialCapacity - 1;
}

template<typename Operations, typename AEAllocator>
AECachedHashMap<Operations, AEAllocator>::~AECachedHashMap()
{
	AEMemoryAllocator &memAlloc = AEAllocator().Get(this);
	memAlloc._blockFree<Elem>( m_lpElem, ( m_uiHashMod+1 ) );
}

template<typename Operations, typename AEAllocator>
AECachedHashMap<Operations, AEAllocator>& AECachedHashMap<Operations, AEAllocator>::operator=( const AECachedHashMap *lpOther )
{
	// Deallocate our storage
	AEMemoryAllocator &memAlloc = AEAllocator().Get(this);
	memAlloc._blockFree<Elem>( m_lpElem, m_uiHashMod+1 );
	
	// Copy other storage
	this->m_uiHashMod = lpOther->m_uiHashMod;
	this->m_uiNumElems = lpOther->m_uiNumElems;
	m_lpElem = memAlloc._blockAlloc<Elem>( m_uiHashMod+1 );

	hkString::memCpy(m_lpElem, lpOther->m_lpElem, sizeof(Elem)*(m_uiHashMod+1) );

	AEASSERT( this->IsOk() );
	return *this;
}

template<typename Operations, typename AEAllocator>
typename AECachedHashMap<Operations, AEAllocator>::AECachedHashMapIterator AECachedHashMap<Operations, AEAllocator>::GetIterator( void ) const
{
	int i;
	for( i = 0; i <= m_uiHashMod; ++i )
	{
		if( ELEM_HASH(i) != HASH_EMPTY )
		{
			break;
		}
	}
	return reinterpret_cast<AECachedHashMapIterator>( AEUINT32(i) );
}

template<typename Operations, typename AEAllocator>
AEUINT32 AECachedHashMap<Operations, AEAllocator>::GetKey( AECachedHashMapIterator itIter ) const
{
	int i = static_cast<int>( reinterpret_cast<AEUINT32>(itIter) );
	AEASSERT( i>=0 && i<=m_uiHashMod );
	return ELEM_KEY(i);
}

template<typename Operations, typename AEAllocator>
AEUINT32 AECachedHashMap<Operations, AEAllocator>::GetValue( AECachedHashMapIterator itIter ) const
{
	int i = static_cast<int>( reinterpret_cast<AEUINT32>(itIter) );
	AEASSERT( i>=0 && i<=m_uiHashMod );
	return ELEM_VAL(i);
}

template<typename Operations, typename AEAllocator>
void AECachedHashMap<Operations, AEAllocator>::SetValue( AECachedHashMapIterator itIter, AEUINT32 uiValue )
{
	int i = static_cast<int>( reinterpret_cast<AEUINT32>(itIter) );
	AEASSERT( i>=0 && i<=m_uiHashMod );
	ELEM_VAL(i) = val;
}

template<typename Operations, typename AEAllocator>
typename AECachedHashMap<Operations, AEAllocator>::AECachedHashMapIterator AECachedHashMap<Operations, AEAllocator>::GetNext( AECachedHashMapIterator itIter ) const
{
	int i = static_cast<int>( reinterpret_cast<AEUINT32>(itIter) );
	AEASSERT( i>=0 && i<=m_uiHashMod );

	for( i += 1; i <= m_uiHashMod; ++i )
	{
		if( ELEM_HASH(i) != HASH_EMPTY )
		{
			break;
		}
	}
	return reinterpret_cast<AECachedHashMapIterator>( AEUINT32(i) );
}

template<typename Operations, typename AEAllocator>
AEBOOL32 AECachedHashMap<Operations, AEAllocator>::IsValid( AECachedHashMapIterator itIter ) const
{
	int i = static_cast<int>( reinterpret_cast<AEUINT32>(itIter) );
	AEASSERT( i>=0 && i<=m_uiHashMod+1 );
	return i <= m_uiHashMod;
}

template<typename Operations, typename AEAllocator>
void AECachedHashMap<Operations, AEAllocator>::Insert( AEUINT32 uiKey, AEUINT32 uiVal )
{
	AEUINT32 uiHash = m_objOps.uiHash(uiKey);
	AEASSERT( uiHash != HASH_EMPTY );
	// This is quite conservative. We could grow more
	// slowly at the cost of potentially longer searches.
	if( (m_uiNumElems + m_uiNumElems ) > m_uiHashMod )
		_resizeTable(m_uiHashMod + m_uiHashMod + 2);

	AEUINT32 i = uiHash & m_uiHashMod;
	while(1) // find free slot
	{
		if(ELEM_HASH(i) == HASH_EMPTY)
		{
			m_uiNumElems += 1;
			break;
		}
		else if( NOT_EQUAL(i, uiHash, uiKey, m_objOps) )
		{
			i = (i+1) & m_uiHashMod;
		}
		else // overwrite a uiKey
		{
			break;
		}
	}
	
	// Insert uiKey,uiValue
	ELEM_HASH(i) = uiHash;
	ELEM_KEY(i)  = uiKey;
	ELEM_VAL(i)  = val;
}

template<typename Operations, typename AEAllocator>
typename AECachedHashMap<Operations, AEAllocator>::AECachedHashMapIterator AECachedHashMap<Operations, AEAllocator>::FindKey( AEUINT32 uiKey ) const
{
	AEUINT32 uiHash = m_objOps.uiHash(uiKey);
	for(	AEUINT32 i = uiHash & m_uiHashMod;
			ELEM_HASH(i) != HASH_EMPTY;
			i = (i+1) & m_uiHashMod )
	{
		if( Equal(i,uiHash,uiKey,m_objOps) )
		{
			return reinterpret_cast<AECachedHashMapIterator>(i);
		}
	}
	return reinterpret_cast<AECachedHashMapIterator>( AEUINT32(m_uiHashMod+1) ); // not found
}

template<typename Operations, typename AEAllocator>
typename AECachedHashMap<Operations, AEAllocator>::AECachedHashMapIterator AECachedHashMap<Operations, AEAllocator>::FindOrInsertKey( AEUINT32 uiKey, AEUINT32 uiVal )
{
	// reserve space for another element
	if( (m_uiNumElems + m_uiNumElems ) > m_uiHashMod )
		_resizeTable(m_uiHashMod + m_uiHashMod + 2);

	AEUINT32 uiHash = m_objOps.uiHash(uiKey);
	for(AEUINT32 i = uiHash & m_uiHashMod;
		true;
		i = (i+1) & m_uiHashMod )
	{
		if( Equal(i,uiHash,uiKey,m_objOps) )
		{
			return reinterpret_cast<AECachedHashMapIterator>(i);
		}
		else if( ELEM_HASH(i) == HASH_EMPTY )
		{
			ELEM_HASH(i) = uiHash;
			ELEM_KEY(i) = uiKey;
			ELEM_VAL(i) = uiValue;
			m_uiNumElems += 1;
			return reinterpret_cast<AECachedHashMapIterator>(i);
		}
	}
	// not reached
}

template<typename Operations, typename AEAllocator>
AEUINT32 AECachedHashMap<Operations, AEAllocator>::Get( AEUINT32 uiKey, AEUINT32 *lpOut ) const
{
	AECachedHashMapIterator itIter = FindKey(uiKey);
	if( IsValid( itIter ) )
	{
		*lpOut = GetValue( itIter );
		return 1;
	}
	return 0;
}

template<typename Operations, typename AEAllocator>
AEUINT32 AECachedHashMap<Operations, AEAllocator>::GetOrInsert( AEUINT32 uiKey, AEUINT32 uiNotFound )
{
	//TODO: examine table directly - save a lookup
	AECachedHashMapIterator itIter = FindKey(uiKey);
	if( IsValid(itIter) )
	{
		return GetValue( itIter );
	}
	Insert( uiKey,uiNotFound );
	return uiNotFound;
}

template<typename Operations, typename AEAllocator>
AEUINT32 AECachedHashMap<Operations, AEAllocator>::GetWithDefault( AEUINT32 uiKey, AEUINT32 uiDefault ) const
{
	AEUINT32 uiRet = uiDefault;
	Get( uiKey, &uiRet );
	return uiRet;
}

template<typename Operations, typename AEAllocator>
void AECachedHashMap<Operations, AEAllocator>::Remove( AECachedHashMapIterator itIter )
{
	AEUINT32 i = reinterpret_cast<AEUINT32>(itIter);

	// Remove itIter
	--m_uiNumElems;
	ELEM_HASH(i) = HASH_EMPTY;

	// find lowest element of this unbroken run
	AEUINT32 lo = ( i + m_uiHashMod ) & m_uiHashMod;
	while( ELEM_HASH(lo) != HASH_EMPTY )
	{
		lo = ( lo + m_uiHashMod ) & m_uiHashMod;
	}
	lo = ( lo + 1 ) & m_uiHashMod;

	// the slot which has become empty
	AEUINT32 empty = i;
	
	// sift up, closing any gaps we find
	for( i = (i + 1) & m_uiHashMod;
		ELEM_HASH(i) != HASH_EMPTY;
		i = (i+1) & m_uiHashMod )
	{
		AEUINT32 hmod = ELEM_HASH(i) & m_uiHashMod;

		// Three cases to consider here. 
		// a) The normal case where lo <= empty < i.
		// b) The case where i has wrapped around.
		// c) The case where both i and empty have wrapped around.
		// The initial case will be a. (Or b if the last slot is freed).
		// and may progress to b, and finally c.
		// The algorithm will terminate before 'i' reaches 'lo'
		// otherwise the table would have no free slots.
		
		// 'normal'      'i wrapped'   'i and empty wrapped'
		// ===== lo      ===== i       ===== empty
		// ===== empty   ===== lo      ===== i 
		// ===== i       ===== empty   ===== lo     
		
		if( ( i >= lo ) && ( hmod > empty ) )
		{
			continue;					
		}
		else if( ( i < empty ) && ( hmod > empty || hmod <= i ) )
		{
			continue;
		}
		else if( /*i > empty && */ ( hmod > empty && hmod < lo ) )
		{
			continue;
		}
		AEASSERT( i != empty ); // by design
		AEASSERT( i != lo ); // table became full?!

		// copy up
		ELEM_HASH(empty) = ELEM_HASH(i);
		ELEM_KEY(empty)  = ELEM_KEY(i);
		ELEM_VAL(empty)  = ELEM_VAL(i);
		// source slot is now free
		ELEM_HASH(i) = HASH_EMPTY;
		empty = i;
	}
}

template<typename Operations, typename AEAllocator>
AEUINT32 AECachedHashMap<Operations, AEAllocator>::Remove( AEUINT32 uiKey )
{
	AECachedHashMapIterator itIter = FindKey( uiKey );
	if( IsValid( itIter ) )
	{
		Remove( itIter );
		return 1;
	}
	return 0;
}

template<typename Operations, typename AEAllocator>
void AECachedHashMap<Operations, AEAllocator>::_resizeTable( AEINT32 nNewCapacity )
{
	AEASSERT_MSG( m_uiNumElems < newcap, "table size is not big enough" );
	AEASSERT_MSG( HK_NEXT_MULTIPLE_OF(2, newcap) == newcap, "table size should be a power of 2" );

	int oldcap = m_uiHashMod+1;
	Elem* oldelem = m_lpElem;
	AEMemoryAllocator& memAlloc = AEAllocator().Get(this);
	m_lpElem = memAlloc._blockAlloc<Elem>(newcap); // space for values too
	hkString::memSet( m_lpElem, 0xff, sizeof(Elem) * newcap );
	m_uiNumElems = 0;
	m_uiHashMod = newcap - 1;

	for( int i = 0; i < oldcap; ++i )
	{
		if( oldelem[i].uiHash != HASH_EMPTY)
		{
			Insert( oldelem[i].uiKey, oldelem[i].uiValue );
		}
	}

	memAlloc._blockFree<Elem>( oldelem, oldcap );
}

template<typename Operations, typename AEAllocator>
AEBOOL32 AECachedHashMap<Operations, AEAllocator>::IsOk( void ) const
{
	// is count consistent?
	int count = 0;
	int i;
	for( i = 0; i <= m_uiHashMod; ++i )
	{
		count += ELEM_HASH(i) != HASH_EMPTY;
	}
	AEASSERT( count == m_uiNumElems );

	// is element reachable from its uiHash?
	for( i = 0; i <= m_uiHashMod; ++i )
	{
		if( ELEM_HASH(i) != HASH_EMPTY )
		{
			AEUINT32 uiHash = ELEM_HASH(i);
			AEUINT32 uiKey = ELEM_KEY(i);
			AEUINT32 j = uiHash & m_uiHashMod;
			while( NOT_EQUAL(j, uiHash, uiKey, m_objOps) )
			{
				j = (j + 1) & m_uiHashMod;
				AEASSERT( ELEM_HASH(j) != HASH_EMPTY );
			}
		} 
	}
	return true;
}

template<typename Operations, typename AEAllocator>
void AECachedHashMap<Operations, AEAllocator>::Clear( void )
{
	for( int i = 0; i < m_uiHashMod+1; ++i )
	{
		m_lpElem[i].uiHash = HASH_EMPTY;
	}
	m_uiNumElems = 0;
}

template<typename Operations, typename AEAllocator>
void AECachedHashMap<Operations, AEAllocator>::Swap( AECachedHashMap &refOther )
{
	Elem* te = m_lpElem;
	AEUINT32 tn = m_uiNumElems;
	AEUINT32 th = m_uiHashMod;
	m_lpElem = other.m_lpElem;
	m_uiNumElems = other.m_uiNumElems;
	m_uiHashMod = other.m_uiHashMod;
	other.m_lpElem = te;
	other.m_uiNumElems = static_cast<int>(tn);
	other.m_uiHashMod = static_cast<int>(th);
}

template<typename Operations, typename AEAllocator>
void AECachedHashMap<Operations, AEAllocator>::Merge( const AECachedHashMap &refOther )
{
	int ohm = other.m_uiHashMod;
	for( int i = 0; i <= ohm; ++i )
	{
		if( other.m_lpElem[i].uiHash != HASH_EMPTY )
		{
			AEUINT32 uiKey = other.m_lpElem[i].uiKey;
			AEUINT32 val = other.m_lpElem[i].uiValue;
			Insert( uiKey, val );
		} 
	}
}

template<typename Operations, typename AEAllocator>
AEINT32 AECachedHashMap<Operations, AEAllocator>::GetCapacity( void ) const
{
	return m_uiHashMod + 1;
}

template<typename Operations, typename AEAllocator>
void AECachedHashMap<Operations, AEAllocator>::Reserve( AEINT32 nNumElements )
{
	int minCap = numElements * 2; // max 50% occupancy
	int cap = 8;
	while (cap < minCap)
		cap *= 2;

	if( cap > m_uiHashMod+1 ) // only grow
		_resizeTable( cap );
}